from typing import Optional

from list_node import ListNode


class Solution:
    @staticmethod
    def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur is not None:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

    @staticmethod
    def reverse_list_by_recursion(head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        rev = Solution.reverse_list_by_recursion(head.next)
        head.next.next = head
        head.next = None
        return rev